#include <stack>

using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};


class Solution {
public:

    //二叉树的公共祖先
    bool getPath(stack<TreeNode*>& Path, TreeNode* findNode, TreeNode* root)
    {
        if (root == nullptr)
            return false;

        Path.push(root);
        if (root == findNode)
            return true;

        if (getPath(Path, findNode, root->left))
            return true;
        if (getPath(Path, findNode, root->right))
            return true;

        Path.pop();
        return false;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        stack<TreeNode*> pPath;
        stack<TreeNode*> qPath;
        getPath(pPath, p, root);
        getPath(qPath, q, root);

        while (qPath.size() != pPath.size())
        {
            if (qPath.size() > pPath.size())
                qPath.pop();
            else if (qPath.size() < pPath.size())
                pPath.pop();
        }

        while (qPath.top() != pPath.top())
        {
            qPath.pop();
            pPath.pop();
        }

        return qPath.top();
    }

////////////////////////////////////////////////////////////////////////////////////////////

    //二叉树vy双向链表
	void InOrderConvert(TreeNode* cur, TreeNode*& prev)
	{
		if (cur == nullptr)
		{
			return;
		}
		InOrderConvert(cur->left, prev);
		if (prev == nullptr)
		{
			cur->left = prev;
		}
		else  
		{
			cur->left = prev;
			prev->right = cur;
		}
		prev = cur;
		InOrderConvert(cur->right, prev);   
	}

    TreeNode* Convert(TreeNode* pRootOfTree) {
        TreeNode* prev = nullptr;
		InOrderConvert(pRootOfTree, prev);
		TreeNode* head = pRootOfTree;
		while (head != nullptr && head->left != nullptr)
		{
			head = head->left;
		}
		return head;
    }
};